import javax.jws.Oneway;
import java.lang.management.BufferPoolMXBean;
import java.util.Base64;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-03-21
 * Time: 22:51
 */
public class AVLTree {

    public TreeNode root;// 根节点
    static class TreeNode{
        public int val;
//        每个节点需要记录他的平衡因子, 方便后面判断是不是平衡
//        balanceFactor = 右子树的高度 -  左子树的高度
        public int balanceFactor;
        public TreeNode left=null;
        public TreeNode right=null;
//        注意每个节点还需要指向他的父亲节点
        public TreeNode parent=null;
        public TreeNode(int val){
            this.val=val;
        }
    }


    public boolean insert(int val){
        TreeNode node=new TreeNode(val);
//        根为空, 那么新插入的这个节点就是根节点
        if(root==null){
            root=node;
            return true;
        }
//        根节点不为空
        TreeNode parent=null; // 用来记录当前节点的父亲节点
        TreeNode cur=root;
        while(cur!=null){
            parent=cur;
            if(cur.val<val){
                cur=cur.right;
            }else if(cur.val==val){
//                出现相等的值, 直接返回　false
                return false;
            }else{
                cur=cur.left;
            }
        }
//        这里不能这么判断,因为最后 cur 为空, 那么可能 parent 的左右均为空
//        if(cur==parent.left){
//            parent.left=node;
//        }else{
//            parent.right=node;
//        }
        if(parent.val<val){
            parent.right=node;
        }else{
            parent.left=node;
        }

        node.parent=parent;
//        插入之后开始调节平衡因子, 从 parent 开始调
        cur=node;
        while(parent!=null){
//            添加到 左子树则 -- , 右子树 ++
            if(cur==parent.left){
                parent.balanceFactor--;
            }else{
                parent.balanceFactor++;
            }

//            查看是否调节过后树不平衡了
            if(parent.balanceFactor==0){
//                说明树是平衡的, 直接返回即可
//                上面的平衡因子都不用修改了
                break;
            }else if(parent.balanceFactor==1||parent.balanceFactor==-1){
//                继续向上修改
                cur=parent;
                parent=parent.parent;
            }else{
//                说明树已经不平衡了, 需要通过旋转将树变平衡
//                树不平衡还分 四种情况
                if(parent.balanceFactor==2){
                    if(cur.balanceFactor==1){
//                        插入到 较高右子树的右侧
//                       2,1  同为正, 左单旋
                        rotateLeft(parent);
                    }else{
//                        插入到 较高右子树的左侧
//                        右左双旋
                        rotateRL(parent);
                    }
                }else{
//                    parent.bf==-2
                    if(cur.balanceFactor==-1){
//                        插入到 较高左子树的左侧
//                        -2, -1 右单旋
                        rotateRight(parent);
                    }else{
//                        插入到 较高左子树的右侧
//                        左右双旋
                        rotateLR(parent);
                    }
                }
//            上述代码走完就平衡了, 注意及时 break
                break;
            }
        }
        return true;
    }

    /**
     * 左单旋, 一定是 右树高了
     * @param parent
     */
    public void rotateLeft(TreeNode parent){
//        注意不要忘了, 当前 parent 节点也有可能是 其他节点的子节点
        TreeNode pParent=parent.parent;
        TreeNode subR=parent.right;
        TreeNode subRL=subR.left; //右节点的左节点
//        开始旋转, 分三步
//        一: 先把右节点提上来
//        注意不要忘记讨论 parent 原来就是 根的情况
        if(parent==root){
            root=subR;
            subR.parent=null;
        }else{
            if(parent==pParent.left){
                pParent.left=subR;
            }else{
                pParent.right=subR;
            }
            subR.parent=pParent;
        }
//        二: 原来的父亲节点降低
        subR.left=parent;
        parent.parent=subR;
//        三: RL 放在旧的根节点的 右边
        parent.right=subRL;
//        注意 RL 要判空
        if(subRL!= null){
            subRL.parent=parent;
        }
//        修改平衡因子
//        只左单旋的情况下, 只需修改 parent 和 subR , 并且修改后均为 0
        parent.balanceFactor=subR.balanceFactor=0;
    }


    /**
     * 右单旋, 一定是 左树高了
     * @param parent
     */
    public void rotateRight(TreeNode parent){
//        注意不要忘了, 当前 parent 节点也有可能是 其他节点的子节点
        TreeNode pParent=parent.parent;
        TreeNode subL=parent.left;
        TreeNode subLR=subL.right; //左节点的右节点
//        开始旋转, 分三步
//        一: 先把左节点提上来
//        注意不要忘记讨论 parent 原来就是 根的情况
        if(parent==root){
            root=subL;
            subL.parent=null;
        }else{
            if(parent==pParent.left){
                pParent.left=subL;
            }else{
                pParent.right=subL;
            }
            subL.parent=pParent;
        }
//        二: 原来的父亲节点降低
        subL.right=parent;
        parent.parent=subL;
//        三: LR 放在旧的根节点的 左边
        parent.left=subLR;
//        注意 LR 要判空
        if(subLR!= null){
            subLR.parent=parent;
        }
//        修改平衡因子
//        只右单旋的情况下, 只需修改 parent 和 subL , 并且修改后均为 0
        parent.balanceFactor=subL.balanceFactor=0;
    }


    public void rotateLR(TreeNode parent){
        TreeNode subL=parent.left;
        TreeNode subLR=subL.right;
//        因为可以插到 较高左子树的右侧, 这个右侧, 可以是左右的两个节点
//        只要插到这两个节点上, 都会引起 左右双旋
//        并且 对应的平衡因子的调节是不同的情况
        int balanceFactor=subLR.balanceFactor;
        rotateLeft(parent.left);
        rotateRight(parent);
//        调节平衡因子
        if(balanceFactor==-1){
            parent.balanceFactor=1;
            subL.balanceFactor=0;
            subLR.balanceFactor=0;
        }else if(balanceFactor==1){
            parent.balanceFactor=0;
            subL.balanceFactor=-1;
            subLR.balanceFactor=0;
        }
    }


    public void rotateRL(TreeNode parent){
        TreeNode subR=parent.right;
        TreeNode subRL=subR.left;
//        因为可以插到 较高右子树的左侧, 这个左侧, 可以是左右的两个节点
//        只要插到这两个节点上, 都会引起 右左双旋
//        并且 对应的平衡因子的调节是不同的情况
        int balanceFactor=subRL.balanceFactor;
        rotateRight(parent.right);
        rotateLeft(parent);
//        调节平衡因子
        if(balanceFactor==-1){
            parent.balanceFactor=0;
            subR.balanceFactor=1;
            subRL.balanceFactor=0;
        }else if(balanceFactor==1){
            parent.balanceFactor=-1;
            subR.balanceFactor=0;
            subRL.balanceFactor=0;
        }
    }


//    中序遍历有序, 能说明是 二叉搜索树
    public void inOrder(TreeNode root){
        if(root==null){
            return ;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

//    求树的高度
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return 1+Math.max(leftHeight, rightHeight);
    }

//    判断是不是平衡二叉树
    public boolean isBalanced(TreeNode root){
        if(root==null){
            return true;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
//       注意这里不要忘记判断  平衡因子是否正确
        if(rightHeight-leftHeight!=root.balanceFactor){
            System.out.println(root.val+"这个节点"+"的平衡因子有问题");
        }
        return Math.abs(rightHeight-leftHeight)<=1&&
                isBalanced(root.left)&&isBalanced(root.right);
    }
}
